package com.solming.leetcode.question;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
//46. 全排列
public class Permute46 {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        //存选择
        LinkedList<Integer> chooseList = new LinkedList<>();

        choose(nums,chooseList,resultList);
        return resultList;

    }


    public static void  choose(int[] nums, LinkedList<Integer> chooseList,  List<List<Integer>> resultList){

        if (chooseList.size() == nums.length){
            //需要重新 new 避免 choose 重新选择，复用一个对象
            resultList.add(new LinkedList<>(chooseList));
            return ;
        }
        for (int i = 0;i<nums.length;i++){

            if (chooseList.contains(nums[i])){
                continue;
            }
            //进入选择 比如到 1-2，进入选择
            chooseList.add(nums[i]);
            choose(nums,chooseList,resultList);
            //取消选择， 上回合选择 3 ，这里就是把 3 取消。，但是又不知道是谁，这里用 LinkList 的链表特性
            chooseList.removeLast();
        }


    }
}
